A portion of the content of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention is in the field of communication apparatus and methods. Generally, the invention relates to processing and organizing digital information for communication from one location to another. More specifically, this invention relates to use of asynchronous transfer mode in a communication network to communicate information. The communicated information is processed and organized in apparatus and according to methods disclosed herein. Still more particularly, the present invention relates to an ATM communication system interconnect/termination unit (hereinafter, xe2x80x9cATMCSI/TUxe2x80x9d).
2. Related Technology
Asynchronous Transfer Mode (ATM) is a network protocol which is highly advantageous because it allows high speed transmission of divergent types of data, including digital codes, video, and voice. This is accomplished by breaking down incoming digital data to be transmitted into units of constant size. These units are called cells, and include a 48-octet field containing the actual data; along with a header field, for a total of 53 octets in the cell. A Conversion Sublayer Protocol Data Unit (CS-PDU) may have both a header and a trailer of additional information, and may be as long as 64 K bits The process of communicating these cells involves taking digital data and segmenting it into cell-size units and assembling these units into CS-PDU""s. At interconnections, the CS-PDU""s are segmented and reassembled to route cells to their destinations in accord with the communication traffic load of the network, the class of service for the senders of the cells, and a variety of other parameters familiar to those skilled in the pertinent arts.
The header contains a virtual channel identifier and a virtual path identifier which identify the particular cell and its intended destination, and specify an optimal path through the network along which the cell should be routed to reach its destination. The header can also include numerous other information such as the type of data in the CS-PDU and attributes of the data, the sender and/or the destination. In combination, the virtual path identifier and virtual channel identifier define a virtual circuit within the network. This virtual circuit is unlike the old and well known actual hard-wired communication circuits of conventional telephone and data transmission systems, for example, because it does not actually provide a fixed or constant communication path (i.e., an electrical conductor, twisted-pair conductors, radio link, or fiber-optic light conductor, for example) continuously extending between the end points. A virtual circuit is continually reconfigured (i.e., possibly following a succession of several different alternative network paths) as the operating circumstances of the network change dynamically.
The ATM-protocol data may be transmitted along a digital electronic data network. A series of cells or packets communicated between endpoints of the network effectively provides a communication circuit between these endpoints. Such communication networks are becoming increasing widespread. These networks allow for the communication of divergent types of data including computer-coded text and graphics, voice, music, images, and video. Such networks enable the interconnection of large numbers of computer work stations, telephone, television systems, video teleconferencing systems, and other facilities over common data links or carriers.
Computer work stations are typically interconnected by local area networks (LAN) such as Ethernet, Token Ring, DECNet and RS-232, whereas metropolitan, national and international systems are interconnected by wide area networks (WAN) such as T1, V3.5 and FDDI.
LANs and WANs themselves can be interconnected by devices known as hubs, bridges and routers in an unlimited configuration. Although the distinction between these interconnection devices is becoming increasingly arbitrary, they are officially classified in accordance with the layer in the Open Systems Interconnection (OSI) model in which they operate.
Hubs interconnect devices using the Physical Layer, bridges utilize the Data Link layer, whereas routers operate using the Network layer. Hubs and bridges generally act merely as switches or funnels, whereas routers perform higher level functions including selecting optimal routes through the network for transmission of data packets or cells on an individual basis, and performing network management tasks such as forcing diagnostics operations and controlling other routers or nodes. Whereas hubs and bridges generally operate on data which is formatted in a single protocol such as those listed above (i.e., uni-protocol), routers can typically identify and process data which can be in any one of several protocols (multi-protocol).
Interconnect devices, especially the more sophisticated routers, have typically been large, bulky and expensive units which operate at relatively low speed. As such, they limit the data throughput speed in the network in which they are installed. The reasons why routers have been so slow is that they are generally multi-chip units which transfer data being processed to and from Content Addressable Memory (CAM) chips which are separate from the processor, input/output (I/O) and other functional chips of the unit. These data-transfer operations each require multiple system clock cycles which fundamentally limit the data transfer speed. In addition, multiple latencies are present in the various paths by which data moves through the unit. The degree by which such latencies can be reduced, as well as the degree by which the size and cost of a multi-chip system can be reduced, are also fundamentally limited.
It should be recalled that the digital communication connections (i.e., virtual circuits) maintained by an ATM system may belong to different classes of service. The reasons for these differing classes of service have to do with the differing types of digital data being communicated. Video connections, for example, do not require the same class of service as do file transfers. A file transfer is not sensitive to delay, while a video connection certainly is sensitive to transmission delay. Similarly, an audio connection is not sensitive to cell loss, while a file transfer is very sensitive to cell loss. With an audio connection, the loss of a cell in not noticeable to the recipient of the conversation because the human ear is not sensitive enough to detect the small gap in the conversation. The human ear takes meaning from context, so that a small gap in the sound of a word would probably not even be noticed. On the other hand, a file transfer is very sensitive to loss of a cell. A missing cell from a file transfer means that the received file is deficient and incomplete, and that the file data may be meaningless without the missing data.
Consequently, differing classes of service are provided to users of ATM systems. One class of service is constant-bit-rate (CBR) service, and is commonly used for audio communications and un-compressed video information. With constant-bit-rate service a cell is transmitted from a given connection on a regularly repeating time interval, perhaps one cell every couple of microseconds. Another class of service is variable-bit-rate (VBR) service, and is commonly used to transmit compressed video data. The cell rate in this instance is variable dependent on the video compression technique in use and the video image contents (i.e., rate of video image change or frames per second). Understandably, managing these variable-bit-rate services becomes a burdensome task when a multitude of connections (perhaps in the thousands) are being maintained simultaneously.
A conventional asynchronous transfer mode (ATM) speech-path switching system is depicted in U.S. Pat. No. 4,956,839, issued Sep. 11, 1990 to Torii Yutaka, et al. The ""839 patent is believed to disclose an ATM line terminating apparatus serving to physically terminate a transmission line and to perform processing of received information in ATM format. That is, information contained in a header filed of a received cell or packet is processed. The ATM terminating apparatus includes a cell-phase synchronizing circuit for matching the temporal positions of cells in each of the lines; and a flow monitor circuit for performing control to avoid overload of the subscriber terminal according to a service agreement, for example.
Another conventional ATM switch and multiplexer is known in accord with U.S. Pat. No. 5,189,668, issued Feb. 23, 1993 to Mashiro Takatori, et al. The ""668 patent is believed to disclose an ATM switch having a plurality of concentration space-division switches each constituted with an multi-stage connection of switch modules. Each of the switch modules in a stage includes a certain number of buffers and a selector for arbitrating outputs from the buffers. Each stage includes switch modules of a number at most equal to the certain number of buffers of the stage multiplied by the number of switch modules in a preceding stage. The multiple stages include a final stage with a singular switch module.
Still another conventional ATM switching system and adaptation processing apparatus is disclosed in U.S. Pat. No. 5,214,642, issued May 25, 1993 to Masao Kunimoto, et al. The ATM apparatus of the ""642 patent is believed to include an adaption-processing apparatus for assembling received data units of fixed length to provide variable-length data units. These variable-length data units are transmitted to a plurality of variable-length data unit processors while assembling variable-length data units received from the plurality of variable-length data unit processors to provide fixed-length data units for transmission therefrom. This ATM switching system includes an adaptation processing apparatus, a signal processing unit having a plurality of the variable-length data unit processors, and first-in-first-out (FIFO) memory for the variable-length data units provided from the adaptation process.
Further, a conventional ATM network device is known in accord with U.S. Pat. No. 5,220,563, issued Jun. 15, 1993 to Thierry Grenot, et al. The ""563 patent is believed to relate to a device for acquiring the signalling data elements of each channel of multi-frame data, and for detecting the changes in state of these data elements. A device generates an information cell on the network for each change thus detected, with the information cell including the new signalling data elements. The information cell also includes the address information associated with the corresponding channel. A device is included for receiving and memorizing the information cells from the network, and for inserting the data elements thus memorized into a multi-frame for transmission synchronously in out-of-band mode.
Another interconnection system to which the invention generally relates is disclosed in U.S. Pat. No. 5,218,680, issued Jun. 8, 1993 to J. Farrell et al.
Generally, the conventional technology for ATM termination and interconnection devices can be characterized as offering users only two choices in architecture. One architecture implemented all functions in hardware and was not flexible to evolving technology and situations as the uses of ATM develop. The other architecture executed all commands in software, so that the users of the device could program their choices with respect to how the device functioned in particular situations. However, because all of the commands and CS-PDU processing operations were performed in software by using a processing unit, the devices were slow, and represented a bottleneck in the system. That is, under conditions of heavy or complex traffic, the processor simply was not able to execute enough instructions and process enough CS-PDU""s to keep up with demand.
In ATM technology there is a concept of virtual connections. These might be though of as a virtual pipeline connecting users of the network, but each pipeline serves more than one pair of users. That is, traffic from several users flows along the same pipeline interspersed with one another in fragments. As an example, a computer video session between two users might go through one pipeline, while a file transfer between two other users is also going on through the same pipeline. Each of these communications would use different virtual connections, although they would both go through the same physical structure (i.e., fiber optic cable or twisted-pair telephone lines, for example). In the conventional technology, all the processing could be commanded by software (with the speed limitation alluded to above), or by hardware (with the ATM system having a rigidity in its nature because changing the abilities of the system required new hardware).
A disadvantage of the related technology arises from old methods of implementing a first-in-first-out (FIFO) memory. Traditionally, FIFO memories have been implemented by using one of a xe2x80x9cfall throughxe2x80x9d, or a xe2x80x9cmemory and counterxe2x80x9d architectures. With a fall through architecture, a set of cascaded registers are used, and new data entered into the FIFO falls through the registers until it reaches the last free location. When data is read from the FIFO memory, it is taken from the bottom register, and the content of the other higher registers has to be rewritten successively one register down in the cascade of registers. In the memory and counter implementation, of a FIFO memory, a memory area with register locations, along with separate read and write counters, are maintained. Data elements are written into memory register locations pointed to by the write counter, and read from locations pointed to by the read counter. The counters are individually incremented one register location along the list after each respective read or write operation. After reaching the end of list, the counters rotate individually to the beginning of the memory register locations so that FIFO operation is maintained.
A disadvantage of these conventional FIFO memory implementations results from the inability to either insert new data into the memory, or to remove data from the memory, except at the tail or head end of the list, respectively. However, in ATM operations, including SAR operations in association with receiving or transmitting cells, it is necessary to alter the order of cell reassembly and transmission, for example, in response to the requirements to provide differing classes of ATM service, and to prevent loss of cells from an un-interruptable service during intervals of network conflict or congestion.
Another disadvantage of the conventional technology stems from the conventional calendar structures used to schedule future events in the device. The conventional calendar structures include an array of cell slots with an event pointer that advances one array position for each cell slot time interval. Events that need to be scheduled at a future time have their event descriptor attached to the appropriate location in the array. This attachment may be effected by use of a linked list, for example. When the event pointer gets to the location of a particular event, the event is then scheduled. In case more than one event is. scheduled in the same cell slot, then the event descriptors for the events are linked together by means of the linked list structure. A significant disadvantage of the conventional calendar method is that memory requirements are excessive. For example, if the rates of events to be supported is large, a minimum rate of 1 cell/sec for an OC-3 link at 150 mbps, for example, requires an array of 353,000 entries. Because each entry has a head and a tail pointer with four bytes for each, the total memory requirement is 2.82 Mbytes just for a calendar.
In view of the deficiencies of the conventional technology for ATM systems, a primary object is to avoid one or more of these deficiencies.
An additional object is to provide an ATM interconnection and termination device which combines the features of software programmability and hardware-implemented speed in processing CS-PDU""s received or for transmission.
In view of the deficiencies and limitations of the related conventional technology, there is a need for an ATM interconnection and termination unit which can meet 155 mega-bits per second (MB/s) full-duplex operation rates, while performing segmentation and reassembly (SAR) of AALS CS-PDU""s.
Further to the above, an object of this invention is to provide a ATMCSI/TU in which certain functions that conventionally were performed in firmware which are now performed in a specialized enhanced direct memory access (EDMA) module.
Accordingly, an object for this invention is to provide an ATMCSI/TU in which a memory-resident data structure provides an interface between the ATM software protocol engines, ATM hardware protocol engines, and coprocessor functions that may include multiple hardware elements. The data structure includes one data structure per transmit virtual circuit connection, and one cell per reception virtual circuit connection.
Still further, an object for this invention is to provide such a ATMCSI/TU in which the EDMA is utilized as a specialized high-speed hard-wired AAL5 SAR engine.
Additionally, on object of this invention is to provide such a ATMCSI/TU in which other ATM adaptation layers, such as AAL1, and AAL3/4, are supported with a minimum of involvement from the imbedded processor of the ATMCSI/TU.
Accordingly, an ATMCSI/TU embodying the present invention is implemented on a single integrated circuit chip. The single-chip ATMCSI/TU system includes an ATM processing unit (APU) based on a 32-bit superscalar MIPS central processing unit (CPU), preferably operating at 66 MHz to provide 100 MIPS; a 32-bit, 66 MHz EDMA engine with hardware support for AAL5; master-and-slave Utopia Level 2, multi-PHY ATM cell interface; a timer unit with real-time timers; a scheduler unit; a primary port interface; and a secondary port interface.
An additional object for this invention is to provide such a single-chip ATMCSI/TU system in which the processor memories and the cell buffer memory RAM are included in the single-chip ATMCSI/TU.
Advantages of the present invention include the provision of high-functionality primitives as an interface mechanism between the hardware and software functions. The primitives will be seen to reduce the computational burden on the CPU. Also, the primitives allow implementation in either hardware or software of buffer memory management schemes. Additionally, a primitive in the VC descriptor allows scheduler schemes to be implemented in either hardware or software. A hardware scheduler can build a linked list of VCD""s identifying cells of CS-PDU""s to be transmitted. The SAR engine uses this linked list to determine which VC to transmit next, and as long as the scheduler stays ahead of the SAR engine, no software intervention is required. An arbitrary number of VC""s is supported, in contrast to conventional technologies which have a fixed number of VC""s which can be supported.
An additional object for this invention is to provide an ATMCSI/TU using a single architecture which is capable of implementing almost any conceivable flow-control algorithm for ATM applications.
Another object for this invention is to provide such an ATMCSI/TU in which a programmable CPU is tightly coupled to multiple hardware-coprocessors. The interface between the CPU and the hardware coprocessors is to be defined by multiple data structures which provide bi-directional control and status signalling between the multiple hardware elements and the CPU.
Accordingly, the present ATMCSI/TU provides a virtual circuit descriptor, a buffer descriptor, and hardware registers providing an interface between multiple hardware and software elements of the ATMCSI/TU. This data structure permits the concurrent execution of a flow control algorithm in both software and hardware elements.
In view of the above, the present ATMCSI/TU provides a floating point multiplier unit with extensions for ATM Forum format, other flow control specific CPU instructions, general purpose timers, and a SAR engine discriminator capable of stripping out flow-control-related cell traffic from the ordinary data path cell traffic.
An additional advantage of the present invention is that it allows the flexibility to change flow control algorithms by running a different software algorithm. Also, multiple simultaneous algorithms may be run so that flow control may be determined by a selected or most advantageous method. Also, this flexibility allows the flow control algorithm to be changed on a per-VC basis during system operation. The flexibility of the system allows also an achievement of an optimized split between hardware implemented computationally-intensive operations, and flow-control specific operations which are implemented in software.
Still another object for this invention is to provide. an ATMCSI/TU which will support either a user-defined soft-ware implemented buffer memory management scheme, or a default hard-ware implemented efficient buffer memory management scheme. That is, a user of the ATMCSI/TU may select a software-coded memory management scheme, or may allow the ATMCSI/TU to default to an internal software-driven efficient buffer memory management scheme.
Thus, an advantage of the invention is that buffer memory management can be implemented on a per-VC basis. For applications which run on a dynamic memory environment this implementation has become important. For example, if memory resources are low, then it may be an advantage to switch buffer memory allocation algorithms. Also, providing different buffer management schemes on an ATM-layer-service-category basis may be an advantage. The present invention allows these options. Further, the memory management scheme is run on a time-modified basis. That is, if the software implemented user-defined management scheme misses a time deadline, then the system defaults to the internal efficient scheme to assign the buffer memory addresses as required.
Yet another object for this invention is to provide an ATMCSI/TU having a linked-list implementation of first-in-one-out memory for the SAR cell-buffer memory.
An advantage of the invention is that the FIFO memory as implemented in a linked list format allows easily including data elements in the middle of the FIFO structure; and the deleting of data elements from within the FIFO data structure, with the remainder of the FIFO linked list being undisturbed. There is no need to copy data elements from one memory location to another when manipulating data. Simply changing the content of linked-list linking registers in the linked list memory structure will serve to manipulate the data in its present memory locations.
Still another object for this invention is to provide an ATMCSI/TU having a hierarchical calendar. That is, rather than using a conventional memory-intensive flat calendar with respect to which an event pointer moves at a fixed rate for determining when the time has arrived to transmit cells from a connection for purposes of traffic shaping, the present invention provides a hierarchical calendar using far less memory.
Accordingly, the present invention provides an ATMCSI/TU having a calendar structure of at least two levels (i.e., hierarchies), and with separate pointers at the levels, the pointer of the lowest level moving from location to location with a time period equal to a single cell slot interval; and the pointer of the next higher level moving from location to location with a time period equal to the number of locations in the lower level multiplied by the single cell slot interval.
An advantage of this aspect of the invention results from the reduction in memory requirements for the calendar. That is, the ATM system can realize a wide range of memory-requirement versus processing-requirement tradeoffs. A reduction in memory requirement may come at the expense of increased processing requirements, and vice versa, but the user of the ATMCSI/TU who has a good idea of the traffic profile to be supported may choose appropriate sizes for the levels of the calendar such that system overhead in memory and processing requirements are not excessive.
Still further, the present invention has as an object the provision of an ATMCSI/TU having a scheduler-based and variable transmission interval technique for traffic shaping of a variable-bit-rate (VBR) traffic stream.
Accordingly, the present invention provides an ATMCSI/TU having a scheduler-based implementation of a traffic shaper rather than a more conventional timer-based traffic shaper.
An advantage of the scheduler-based traffic shaping carried out by the present invention is a reduction in CPU workload, and an increased data transfer rate.